Number of corner rectangles

Time: O(NxM^2); Space: O(NxM); medium

Given a grid with only 0 and 1, find the number of corner rectangles.

Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

The number of rows and columns of grid will each be in the range [1, 200][1,200].

Each grid[i][j] will be either 0 or 1.

The number of 1s in the grid will be at most 6000.

Example 1:

Input: grid =

[
  [1, 0, 0, 1, 0],
  [0, 0, 1, 0, 1],
  [0, 0, 0, 1, 0],
  [1, 0, 1, 0, 1]
]

Output: 1

Explanation:

There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

Example 2:

Input: grid =

[
  [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1]
]

Output: 9

Explanation:

There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = [[1,1,1,1]]

Output: 0

Explanation:

  • Rectangles must have four distinct corners.

[3]:

class Solution1(object):
    """
    Time: O(N*M^2), N is the number of rows with 1s, M is the number of cols with 1s
    Space: O(N*M)
    """
    def countCornerRectangles(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rows = [[c for c, val in enumerate(row) if val]
                for row in grid]
        result = 0

        for i in range(len(rows)):
            lookup = set(rows[i])

            for j in range(i):
                count = sum(1 for c in rows[j] if c in lookup)
                result += count*(count-1)//2

        return result

[4]:

s = Solution1()

grid = [
  [1, 0, 0, 1, 0],
  [0, 0, 1, 0, 1],
  [0, 0, 0, 1, 0],
  [1, 0, 1, 0, 1]
]
assert s.countCornerRectangles(grid) == 1

grid = [
  [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1]
]
assert s.countCornerRectangles(grid) == 9

grid = [[1,1,1,1]]
assert s.countCornerRectangles(grid) == 0